package com.lun.hard;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Queue;

import com.lun.util.BinaryTree.TreeNode;

public class SerializeAndDeserializeBinaryTree {
	
	//方法一：自己写的，BFS
	public static class Codec {

	    // Encodes a tree to a single string.
	    public String serialize(TreeNode root) {
	    	if(root == null) return "";
	    	StringBuilder sb = new StringBuilder();
	    	LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
	    	
	    	queue.offer(root);
	    	
	    	int maxDepth = maxDepth(root);
	    	int currentDepth = 0;
	    	
	    	while(!queue.isEmpty()) {
	    		currentDepth++;
	    		for(int size = queue.size(); size > 0; size--) {
	    			TreeNode node = queue.poll();
	    			sb.append(node != null ? node.val : "N");
	    			sb.append(',');
	    			
	    			if(node != null && currentDepth != maxDepth) {
	    				queue.offer(node.left);
	    				queue.offer(node.right);
	    			}
	    		}
	    	}
	    	
	        return sb.substring(0, sb.length() - 1);
	    }
	    
	    private int maxDepth(TreeNode node) {
	    	if(node == null) return 0;
	    	return 1 + Math.max(maxDepth(node.left), maxDepth(node.right));
	    }
	    

	    // Decodes your encoded data to tree.
	    public TreeNode deserialize(String data) {
	    	
	    	if(data == null || data.strip().isEmpty())
	    		return null;
	    	
	    	TreeNode root = null, parent = null;
	    	boolean pollFlag = true, sign = false;
	    	Integer value = null;
	    	LinkedList<TreeNode> queue = new LinkedList<TreeNode>();
	    	for(int i = 0; i <= data.length(); i++) {
	    		if(i == data.length() || data.charAt(i) == ',') {
	    			
	    			TreeNode node = null;
	    			if(value != null) {
	    				node = new TreeNode(value * (sign ? -1 : 1));
	    				if(root == null) {
	    					root = node;
	    					queue.offer(root);
	    					value = null;
	    					continue;
	    				}
    				}
    				
					if(pollFlag) {
						parent = queue.poll();
						if(value != null) {
							parent.left = node;
							queue.offer(node);
						}
					}else {
						if(value != null) {
							parent.right = node;
							queue.offer(node);
						}
					}
					pollFlag = !pollFlag;
	    			value = null;
	    			sign = false;
	    		}else {
	    			if(data.charAt(i) != 'N') {
	    				if(data.charAt(i) == '-') {
	    					sign = true;
	    					continue;
	    				}
	    				if(value == null) value = 0;
	    				value = value * 10 + data.charAt(i) - '0'; 
	    			}
	    		}
	    	}
	    	
	    	return root;
	    }
	}
	
	//方法二：别人写的，前序遍历模式
	public static class Codec2 {
	    private static final String spliter = ",";
	    private static final String NN = "X";

	    // Encodes a tree to a single string.
	    public String serialize(TreeNode root) {
	        StringBuilder sb = new StringBuilder();
	        buildString(root, sb);
	        return sb.toString();
	    }

	    private void buildString(TreeNode node, StringBuilder sb) {
	        if (node == null) {
	            sb.append(NN).append(spliter);
	        } else {
	            sb.append(node.val).append(spliter);
	            buildString(node.left, sb);
	            buildString(node.right,sb);
	        }
	    }
	    // Decodes your encoded data to tree.
	    public TreeNode deserialize(String data) {
	        Deque<String> nodes = new LinkedList<>();
	        nodes.addAll(Arrays.asList(data.split(spliter)));
	        return buildTree(nodes);
	    }
	    
	    private TreeNode buildTree(Deque<String> nodes) {
	        String val = nodes.remove();
	        if (val.equals(NN)) return null;
	        else {
	            TreeNode node = new TreeNode(Integer.valueOf(val));
	            node.left = buildTree(nodes);
	            node.right = buildTree(nodes);
	            return node;
	        }
	    }
	}
	
	//方法三：别人写的，BFS
	public static class Codec3 {
	    public String serialize(TreeNode root) {
	        if (root == null) return "";
	        Queue<TreeNode> q = new LinkedList<>();
	        StringBuilder res = new StringBuilder();
	        q.add(root);
	        while (!q.isEmpty()) {
	            TreeNode node = q.poll();
	            if (node == null) {
	                res.append("n ");
	                continue;
	            }
	            res.append(node.val + " ");
	            q.add(node.left);
	            q.add(node.right);
	        }
	        return res.toString();
	    }

	    public TreeNode deserialize(String data) {
	        if (data == "") return null;
	        Queue<TreeNode> q = new LinkedList<>();
	        String[] values = data.split(" ");
	        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
	        q.add(root);
	        for (int i = 1; i < values.length; i++) {
	            TreeNode parent = q.poll();
	            if (!values[i].equals("n")) {
	                TreeNode left = new TreeNode(Integer.parseInt(values[i]));
	                parent.left = left;
	                q.add(left);
	            }
	            if (!values[++i].equals("n")) {
	                TreeNode right = new TreeNode(Integer.parseInt(values[i]));
	                parent.right = right;
	                q.add(right);
	            }
	        }
	        return root;
	    }
	}
	
}
